package edu.kit.csl.pisa.datatypes;

/*
This file is part of the PISA Alignment Tool.

Copyright (C) 2013
Karlsruhe Institute of Technology
Cognitive Systems Lab (CSL)
Felix Stahlberg

PISA is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

PISA is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with PISA. If not, see <http://www.gnu.org/licenses/>.
*/

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;

import edu.kit.csl.pisa.io.Logger;
import edu.kit.csl.pisa.ui.Configuration;
import eva2.tools.math.RNG;

/**
 * This class represents an alignment, that is basically an alignment in terms
 * of (Brown et. al., 1994) plus word boundary markers. Note that there is no
 * reference to the corresponding source and target language sentences here
 * (they have to be provided by the context if necessary) in order to reduce
 * space complexity. It rather encapsulates the intrinsic state of 
 * {@link SentenceAlignment} flyweights. 
 * TODO: Bad Smell: God class
 * 
 * @see SentenceAlignment
 * @see SentencePair
 */
public class Alignment {

	/*
	 * Number of target words.
	 */
	protected short nTrgtWords;
	
	/*
	 * Number of free (non-locked) target words
	 */
	protected short nFreeTrgtWords;
	
	/*
	 * Number of free (non-locked) phonemes
	 */
	protected short nFreePhonemes;
	
	/*
	 * Fertilities (array over source words)
	 */
	protected byte[] fertilities;
	
	/*
	 * Alignment vector (like in (Brown et. al., 94)) on word level.
	 */
	protected short[] wordAlignment;
	
	/*
	 * Start positions of target words in the target phoneme sequence (array 
	 * over target words). At the end there is a guardian element.
	 */
	protected short[] startPositions;
	
	/*
	 * True for locked target word indexes.
	 */
	protected boolean[] locks;
	
	/*
	 * Relative target word positions (relative to all target words aligned to
	 * the same source word) (array over target words).
	 */
	protected byte[] relTrgtPositions;
	
	/*
	 * The max word length parameter.
	 */
	protected static int maxWordLength = -1;
	
	/*
	 * The max fertility parameter.
	 */
	protected static int maxFertility = -1;
	
	/*
	 * The max fertility parameter.
	 */
	protected static int maxNeighborhoodSize = -1;
	
	/**
	 * This is the copy constructor. All internal arrays are cloned, so the
	 * new alignment is a self-contained copy.
	 * 
	 * @param a Alignment to copy
	 * @throws NullPointerException if a is null
	 */
	public Alignment(Alignment a) {
		copy(a);
	}
	
	/*
	 * Clones the parameters of the given alignment and stores them here
	 */
	private void copy(Alignment a) {
		nTrgtWords = a.nTrgtWords;
		nFreeTrgtWords = a.nFreeTrgtWords;
		nFreePhonemes = a.nFreePhonemes;
		fertilities = a.fertilities.clone();
		wordAlignment = a.wordAlignment.clone();
		locks = a.locks.clone();
		startPositions = a.startPositions.clone();
		relTrgtPositions = a.relTrgtPositions.clone();
	}
	
	/**
	 * This constructor creates an empty alignment. The last target word is 
	 * per default aligned to all phonemes.
	 * 
	 * @param srcLen length of the source language sentence
	 * @param nTrgtPhonemes length of the target language phoneme sequence
	 * @param nTrgtWords number of target language words
	 */
	public Alignment(int srcLen, short nTrgtPhonemes, int nTrgtWords) {
		assert nTrgtPhonemes >= nTrgtWords;
		fertilities = new byte[srcLen];
		wordAlignment = new short[nTrgtWords];
		startPositions = new short[nTrgtWords + 1];
		locks = new boolean[nTrgtWords];
		relTrgtPositions = new byte[nTrgtWords];
		startPositions[nTrgtWords] = nTrgtPhonemes; // Guardian
		this.nTrgtWords = (short) nTrgtWords;
		nFreeTrgtWords = this.nTrgtWords;
		nFreePhonemes = nTrgtPhonemes;
	}
	
	/**
	 * This constructor creates the alignment data structure from an alignment
	 * vector (as in (Brown et. al., 94)) and an boolean array, which defines
	 * for each phoneme in the target sequence if there is a word boundary
	 * or not. If there is a marker on the i-th position, it means that there
	 * is a word boundary between the (i-1)-th and i-th phoneme. The length of 
	 * the target language sentence is fetched from the length of the given 
	 * arrays.
	 * 
	 * @param srcLen length of the source language sentence
	 * @param alignment 
	 * @param wordBoundaries
	 */
	public Alignment(int srcLen, short[] alignment, boolean[] wordBoundaries) {
		initialize(srcLen, alignment, wordBoundaries, 
				new boolean[alignment.length]);
	}
	
	/**
	 * This constructor creates the alignment data structure from an alignment
	 * vector (as in (Brown et. al., 94)) and an boolean array, which defines
	 * for each phoneme in the target sequence if there is a word boundary
	 * or not. If there is a marker on the i-th position, it means that there
	 * is a word boundary between the (i-1)-th and i-th phoneme. The length of 
	 * the target language sentence is fetched from the length of the given 
	 * arrays.
	 * 
	 * @param srcLen length of the source language sentence
	 * @param alignment 
	 * @param wordBoundaries
	 * @param phonemeLocks If this array contains true for a start position of 
	 * 		the target language word, the corresponding alignment point is 
	 * 		locked and won't be modified (l modifier in PISA alignment files)
	 */
	public Alignment(int srcLen, short[] alignment, boolean[] wordBoundaries,
			boolean[] phonemeLocks) {
		initialize(srcLen, alignment, wordBoundaries, phonemeLocks);
	}
	
	/* (non-Javadoc)
	 * Constructor helper method.
	 */
	private void initialize(int srcLen, short[] alignment, boolean[] wordBoundaries,
			boolean[] phonemeLocks) {
		assert alignment.length == wordBoundaries.length;
		assert alignment.length == phonemeLocks.length;
		final short trgtLen = (short) alignment.length;
		if (maxWordLength < 0) {
			maxWordLength = Configuration.getSingleton().getInteger(
					"maxWordLength");
			maxFertility = Configuration.getSingleton().getInteger(
					"maxFertility");
			maxNeighborhoodSize = Configuration.getSingleton().getInteger(
					"maxNeighborhoodSize");
		}
		// Count word boundaries
		wordBoundaries[0] = true;
		nTrgtWords = 0;
		for (boolean boundary : wordBoundaries) {
			if (boundary) {
				nTrgtWords++;
			}
		}
		nFreeTrgtWords = nTrgtWords;
		fertilities = new byte[srcLen];
		wordAlignment = new short[nTrgtWords];
		startPositions = new short[nTrgtWords + 1];
		locks = new boolean[nTrgtWords];
		relTrgtPositions = new byte[nTrgtWords];
		
		startPositions[nTrgtWords] = trgtLen; // Guardian
		int curTrgtWord = -1;
		for (short i = 0; i < trgtLen; i++) {
			if (wordBoundaries[i]) {
				curTrgtWord++;
				short srcWordPos = alignment[i];
				startPositions[curTrgtWord] = i;
				locks[curTrgtWord] = phonemeLocks[i];
				if (locks[curTrgtWord]) {
					nFreeTrgtWords--;
				}
				relTrgtPositions[curTrgtWord] = fertilities[srcWordPos]++;
				wordAlignment[curTrgtWord] = srcWordPos;
			}
		}
		// Calculate nFreePhonemes
		nFreePhonemes = trgtLen;
		for (short i = 0; i < nTrgtWords; i++) {
			if (locks[i]) {
				nFreePhonemes -= (startPositions[i + 1] - startPositions[i]);
			}
		}
	}
	
	/**
	 * Note: This method assumes that the given Alignment instances are
	 * internally consistent (no contradictions for example between
	 * wordAlignment and fertility arrays). Locks are ignored.
	 * {@inheritDoc}
	 * @see #isConsistent(int, int)
	 */
	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof Alignment)) {
			return false;
		}
		Alignment a = (Alignment) obj;
		if (nTrgtWords != a.nTrgtWords 
				|| fertilities.length != a.fertilities.length) {
			return false;
		}
		for (short i = 0; i < nTrgtWords; i++) {
			if (wordAlignment[i] != a.wordAlignment[i]
					|| startPositions[i] != a.startPositions[i]) {
				return false;
			}
		}
		return true;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = prime + Arrays.hashCode(startPositions);
		result = prime * result + Arrays.hashCode(wordAlignment);
		return result;
	}

	/**
	 * Get the number of words in the target language sentence.
	 * 
	 * @return number of words on the target side
	 */
	public int countTargetWords() {
		return nTrgtWords;
	}
	
	/**
	 * Get the number of words in the source language sentence.
	 * 
	 * @return number of words on the source side
	 */
	public int countSourceWords() {
		return fertilities.length;
	}
	
	/**
	 * Get the number of phonemes in the target language sentence.
	 * 
	 * @return number of phonemes on the target side
	 */
	public int countTargetPhonemes() {
		return startPositions[nTrgtWords];
	}
	
	/**
	 * Wrapper method for <code>isConsistent(countSourceWords(),
	 * countTargetPhonemes())</code>.
	 * 
	 * @return <code>true</code> if the alignment is internally consistent
	 * 		<code>false</code> otherwise
	 */
	public boolean isConsistent() {
		return isConsistent(countSourceWords(), countTargetPhonemes());
	}
	
	/**
	 * This method contains some sanity checks assuring that the internal 
	 * structure of this alignment is consistent. This particularly means that
	 * all internal arrays do not contain internal contradictions (like none
	 * monotone start positions) or conflict with other arrays (like that the
	 * fertilities contradict the relative word positions).
	 * 
	 * @param int srcLength length of the source language sentence
	 * @param int trgtLength length of the target language phoneme sequence
	 * @return <code>true</code> if the alignment is internally consistent
	 * 		<code>false</code> otherwise
	 */
	public boolean isConsistent(int srcLength, int trgtLength) {
		Logger log = Logger.getSingleton();
		if (countTargetPhonemes() != trgtLength
				|| countSourceWords() != srcLength
				|| countTargetWords() > trgtLength
				|| startPositions[0] != 0) {
			log.debug("Consistency test fails on first place");
			return false;
		}
		byte[] refFertilities = new byte[srcLength];
		short lastStartPos = -1;
		for (int i = 0; i < nTrgtWords; i++) {
			short srcWordPos = wordAlignment[i]; 
			if (srcWordPos < 0
					|| srcWordPos >= countSourceWords()
					|| startPositions[i] <= lastStartPos
					|| startPositions[i] - lastStartPos > maxWordLength
					|| refFertilities[srcWordPos] != relTrgtPositions[i]) {
				log.debug("Consistency test fails on first place on " + i 
					+ "-th target word (" + srcWordPos + "th source word, "
					+ "start position: " + startPositions[i] + " relative word"
					+ " position: " + relTrgtPositions[i] + ")");
				return false;
			}
			refFertilities[srcWordPos]++;
			lastStartPos = startPositions[i];
		}
		if (startPositions[nTrgtWords] <= lastStartPos
				|| startPositions[nTrgtWords] - lastStartPos > maxWordLength) {
			log.debug("Consistency test fails on last position");
			return false;
		}
		for (int i = 0; i < srcLength; i++) {
			if (refFertilities[i] != fertilities[i]
					|| fertilities[i] > maxFertility) {
				log.debug("Consistency test detects wrong fertility at " + i);
				return false;
			}
		}
		short nFreePhonemesCorrect = (short) countTargetPhonemes();
		short nFreeTrgtWordsCorrect = nTrgtWords;
		for (short i = 0; i < nTrgtWords; i++) {
			if (locks[i]) {
				nFreeTrgtWordsCorrect--;
				nFreePhonemesCorrect -= (startPositions[i + 1] 
						- startPositions[i]);
			}
		}
		if (nFreePhonemesCorrect != nFreePhonemes) {
			log.debug("Consistency test detects wrong nFreePhonemes: Corr:" 
				+ nFreePhonemesCorrect + " but:" + nFreePhonemes);
		}
		if (nFreeTrgtWordsCorrect != nFreeTrgtWords) {
			log.debug("Consistency test detects wrong nFreeTrgtWords: Corr:" 
				+ nFreeTrgtWordsCorrect + " but:" + nFreeTrgtWords);
		}
		return true;
	}
	
	/**
	 * This iterator goes over each position in the French phoneme string. For
	 * each position, corresponding values are encapsulated in 
	 * AlignmentPosition instances.
	 * The extrinsic state of this flyweight has to be passed-through via
	 * function arguments.
	 * 
	 * @param srcSen source sentence
	 * @param trgtSen target sentence (phoneme sequence)
	 */
	public Iterator<AlignmentPosition> eachTargetPhoneme(final Sentence srcSen,
			final Sentence trgtSen) {
        Iterator<AlignmentPosition> it = new Iterator<AlignmentPosition>() {
        	private short phonemePos = -1;
        	private short nextWordPos = 0;
            private int[] src = srcSen.toArray();
            private int[] trgt = trgtSen.toArray();
            private final int len = trgtSen.getLength() - 1;
            private AlignmentPosition ap = new AlignmentPosition();
            
            @Override
            public boolean hasNext() {
            	return phonemePos < len;
            }

            @Override
            public AlignmentPosition next() {
            	if (startPositions[nextWordPos] != ++phonemePos) {
            		ap.moveToNextPhonemePosition(trgt[phonemePos]);
            	} else { // word boundary! new source word
            		short srcWordPos = wordAlignment[nextWordPos]; 
            		ap.moveToNextWordPosition(trgt[phonemePos], 
            				src[srcWordPos],
            				srcWordPos,
            				relTrgtPositions[nextWordPos],
            				(short)(startPositions[nextWordPos+1]-phonemePos));
            		nextWordPos++;
            	}
                return ap;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
		return it;
	}
	
	/**
	 * Use this iterator for iterating over the set of French words. This is
	 * the same as {@link #eachTargetPhoneme()} reduced to phoneme positions
	 * with word beginnings. Note that the trgtPhoneme is always -1. We assume
	 * that the first phoneme of each word has no special dependencies.
	 * 
	 * The extrinsic state of this flyweight has to be passed-through via 
	 * function arguments.
	 * 
	 * @param srcSen source sentence
	 * @param trgtSen target sentence (phoneme sequence)
	 */
	public Iterator<AlignmentPosition> eachTargetWord(final Sentence srcSen,
			final Sentence trgtSen) {
        Iterator<AlignmentPosition> it = new Iterator<AlignmentPosition>() {
        	private short nextWordPos = 0;
            private int[] src = srcSen.toArray();
            private AlignmentPosition ap = new AlignmentPosition();
            
            @Override
            public boolean hasNext() {
            	return nextWordPos < nTrgtWords;
            }

            @Override
            public AlignmentPosition next() {
            	ap.moveToNextWordPosition(-1, 
            		src[wordAlignment[nextWordPos]],
            		wordAlignment[nextWordPos],
            		relTrgtPositions[nextWordPos],
            		(short)(startPositions[nextWordPos+1] - 
            				startPositions[nextWordPos]));
            	nextWordPos++;
                return ap;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
		return it;
	}
	
	/**
	 * This iterator goes through each English word and its fertility.
	 * The extrinsic state of this flyweight has to be passed-through via 
	 * function arguments.
	 * 
	 * @param srcSen source sentence
	 * @param trgtSen target sentence (phoneme sequence)
	 */
	public Iterator<AlignmentSourceWord> eachSourceWord(final Sentence srcSen,
			final Sentence trgtSen) {
        Iterator<AlignmentSourceWord> i = new Iterator<AlignmentSourceWord>() {
        	private short nextWordPos = 0;
            private int[] src = srcSen.toArray();
            private int len = fertilities.length;
            private AlignmentSourceWord asw = new AlignmentSourceWord();
            
            @Override
            public boolean hasNext() {
            	return nextWordPos < len;
            }

            @Override
            public AlignmentSourceWord next() {
            	asw.moveToNextWordPosition(src[nextWordPos],
            		fertilities[nextWordPos]);
            	nextWordPos++;
                return asw;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
		return i;
	}
	
	/**
	 * Get fertility of NULL.
	 * 
	 * @return fertility of the empty word
	 */
	public byte getNullFertility() {
		return fertilities[0];
	}
	
	/**
	 * Counts the misplaced alignment points between the alignments on word
	 * level. If the lengths of the alignments are not equal, we add the
	 * offset to the number of misplaced alignment points.
	 * 
	 * @param a2 alignment to compare
	 */
	public int distanceTo(Alignment a2) {
		final int minLength = Math.min(a2.nTrgtWords, this.nTrgtWords);
		int distance = 0;
		for (int i = 0; i < minLength; i++) {
			if (a2.wordAlignment[i] != this.wordAlignment[i]) {
				distance++;
			}
		}
		distance += Math.abs(a2.nTrgtWords - this.nTrgtWords);
		return distance;
	}
	
	/**
	 * Calls {@link #combine(Alignment, float)} with 0.5.
	 * 
	 * @param a2 the alignment to combine with
	 * @see #combine(Alignment, float)
	 */
	public void combine(Alignment a2) {
		combine(a2, 0.5f);
	}
	
	/**
	 * Combines the alignment with another alignment. The first half of the
	 * alignment is taken from this alignment, the other half from the given
	 * alignment. Which elements are taken from which elements is decided as
	 * follows:<br>
	 * - Get the medium phoneme position p_m<br>
	 * - All target words with start position < p_m are taken from this
	 * 	 alignment<br>
	 * - All target words with start position >= p_m are taken from the
	 * 	 given alignment<br>
	 * Note that this may change the number of target words.
	 * Note also that we assume that the same target words are locked in both
	 * alignments.
	 * 
	 * @param a2 the alignment to combine with
	 * @param rel between 0 and 1 for position p_m
	 * @throws NullPointerException if <code>a2</code> is null
	 */
	public void combine(Alignment a2, float rel) {
		assert rel >= 0f;
		assert rel <= 1f;
		assert isConsistent();
		assert a2.isConsistent();
		final short pm = (short) Math.ceil(this.countTargetPhonemes() 
				* rel); 
		int thisCount = Arrays.binarySearch(this.startPositions,
				0, nTrgtWords + 1, pm);
		if (thisCount < 0) {
			thisCount = -thisCount - 1;
		}
		int a2Index = Arrays.binarySearch(a2.startPositions,
				0, a2.nTrgtWords + 1, pm);
		if (a2Index < 0) {
			a2Index = -a2Index - 1;
		}
		if (thisCount <= 0 || // No contribution of this alignment
			a2.startPositions[a2Index] // Cross-over word would be too long 
				- startPositions[thisCount - 1] > maxWordLength) {
			return; 
		}
		
		final int a2Count = a2.nTrgtWords - a2Index;
		setNTrgtWords((short) (thisCount + a2Count), thisCount);
		System.arraycopy(a2.wordAlignment, a2Index, wordAlignment,
				thisCount, a2Count);
		System.arraycopy(a2.locks, a2Index, locks,
				thisCount, a2Count);
		System.arraycopy(a2.startPositions, a2Index, startPositions,
				thisCount, a2Count + 1);
		if (!rebuildFertilitiesAndRelTrgtPositions()) {
			copy(a2);
		}
		assert isConsistent();
	}
	
	/* (non-Javadoc)
	 * Rebuilds fertilities, relTrgtPositions, and FreeTrgtWords after they got
	 * screwed up after some alignment modification.
	 * 
	 * @returns false if a maxFertility violation was detected, true otherwise
	 */
	private boolean rebuildFertilitiesAndRelTrgtPositions() {
		Arrays.fill(fertilities, (byte) 0);
		nFreeTrgtWords = 0;
		for (int pos = 0; pos < nTrgtWords; pos++) {
			if (!locks[pos]) {
				nFreeTrgtWords++;
			}
			byte fertility = fertilities[wordAlignment[pos]]++;
			if (fertility >= maxFertility) { // Roll back to a2
				return false;
			}
			relTrgtPositions[pos] = fertility;
		}
		return true;
	}
	
	/**
	 * Inserts a new word boundary between phoneme i-1 and i. The new target
	 * language word is aligned to the source word specified by
	 * srcWordPosOffset. For example, insertWordBoundary(1, 0) inserts a new 
	 * word boundary after the first phoneme and aligns the new target word 
	 * (starting at the second phoneme) to the same source word as the first
	 * phoneme. All impacted alignment parameters are changed consistently. 
	 * If there is already a word boundary, we pass-through to 
	 * {@link #realign(int, int)}.
	 * 
	 * @param phonemePos position of the new word boundary
	 * @param srcWordOffset alignment point which should be used for the
	 * 		resulting new word
	 * @see #insertAbsoluteWordBoundary(short, short)
	 */
	public void insertRelativeWordBoundary(short phonemePos, 
			short srcWordOffset) {
		if (phonemePos >=  startPositions[nTrgtWords]) {
			return;
		}
		int trgtWordPos = Arrays.binarySearch(
				startPositions, 0, nTrgtWords, phonemePos);
		if (trgtWordPos >= 0) {
			realign(trgtWordPos, wordAlignment[trgtWordPos + srcWordOffset]);
			return;
		}
		trgtWordPos = -trgtWordPos - 1; // Now we have the index of the 
										// new target word
		short srcWordPos = wordAlignment[trgtWordPos + srcWordOffset - 1];
		insertWordBoundaryCore(phonemePos, trgtWordPos, srcWordPos);
	}
	
	/**
	 * Inserts a new word boundary between phoneme i-1 and i. The new target
	 * language word is aligned to the source word specified by
	 * srcWordPos. For example, insertWordBoundary(1, 4) inserts a new 
	 * word boundary after the first phoneme and aligns the new target word 
	 * (starting at the second phoneme) to the source word at position 4. All 
	 * impacted alignment parameters are changed consistently. If there is 
	 * already a word boundary, we pass-through to {@link #realign(int, int)}.
	 * 
	 * @param phonemePos position of the new word boundary
	 * @param srcWordPos alignment point which should be used for the
	 * 		resulting new word
	 * @see #insertRelativeWordBoundary(short, short)
	 */
	public void insertAbsoluteWordBoundary(short phonemePos, 
			short srcWordPos) {
		if (phonemePos >=  startPositions[nTrgtWords]
				|| srcWordPos < 0 || srcWordPos >= countSourceWords()) {
			return;
		}
		int trgtWordPos = Arrays.binarySearch(
				startPositions, 0, nTrgtWords, phonemePos);
		if (trgtWordPos >= 0) {
			realign(trgtWordPos, srcWordPos);
			return;
		}
		trgtWordPos = -trgtWordPos - 1; // Now we have the index of the 
										// new target word
		insertWordBoundaryCore(phonemePos, trgtWordPos, srcWordPos);
	}
	
	/* (non-Javadoc)
	 * Resize nTrgtWords dependent parameter arrays: wordAlignment, 
	 * startPositions, relTrgtPositions, locks if necessary and set nTrgtWords
	 * to a new value. Note: Does not affect nFreeTrgtWords
	 * 
	 * @param newNTrgtWords new nTrgtWords
	 * @param copyTo number of elements to copy from the old arrays
	 */
	private void setNTrgtWords(short newNTrgtWords, int copyTo) {
		// Resize
		if (newNTrgtWords > wordAlignment.length) {
			short[] newWordAlignment = new short[newNTrgtWords];
			short[] newStartPositions = new short[newNTrgtWords + 1];
			byte[] newRelTrgtPositions = new byte[newNTrgtWords];
			boolean[] newLocks = new boolean[newNTrgtWords];
			System.arraycopy(wordAlignment, 0, newWordAlignment, 0, copyTo);
			System.arraycopy(startPositions, 0, newStartPositions, 0,
					copyTo + 1);
			System.arraycopy(relTrgtPositions, 0, newRelTrgtPositions, 0,
					copyTo);
			System.arraycopy(locks, 0, newLocks, 0, copyTo);
			wordAlignment = newWordAlignment;
			startPositions = newStartPositions;
			relTrgtPositions = newRelTrgtPositions;
			locks = newLocks;
		}
		nTrgtWords = newNTrgtWords;
	}
	
	/* (non-Javadoc)
	 * Encapsulates common functionality for inserting word boundaries.
	 * 
	 * @param phonemePos position of the new word boundary
	 * @param trgtWordPos position of the target word belonging to phonemePos
	 * 		(TODO: isn't it the index of the word after?)
	 * @param srcWordPos source word which should be aligned to the new word
	 */
	private void insertWordBoundaryCore(short phonemePos, int trgtWordPos,
			short srcWordPos) {
		if (fertilities[srcWordPos] + 1 > maxFertility 
				|| locks[Math.max(0, trgtWordPos - 1)]) {
			return;
		}
		setNTrgtWords((short) (nTrgtWords + 1), (int) nTrgtWords);
		// Shift parameters
		final int nFollowUpWords = nTrgtWords - trgtWordPos - 1;
		System.arraycopy(startPositions, trgtWordPos, startPositions,
				trgtWordPos + 1, nFollowUpWords + 1); // +1 for guardian
		System.arraycopy(wordAlignment, trgtWordPos, wordAlignment,
				trgtWordPos + 1, nFollowUpWords);
		System.arraycopy(locks, trgtWordPos, locks,
				trgtWordPos + 1, nFollowUpWords);
		System.arraycopy(relTrgtPositions, trgtWordPos, relTrgtPositions,
				trgtWordPos + 1, nFollowUpWords);
		byte relTrgtPos = fertilities[srcWordPos]++;
		startPositions[trgtWordPos] = phonemePos;
		wordAlignment[trgtWordPos] = srcWordPos;
		locks[trgtWordPos] = false;
		nFreeTrgtWords++;
		for (int i = trgtWordPos + 1; i < nTrgtWords; i++) {
			if (wordAlignment[i] == srcWordPos) {
				relTrgtPositions[i]++;
				relTrgtPos--;
			}
		}
		relTrgtPositions[trgtWordPos] = relTrgtPos;
	}
	
	/**
	 * Deletes the word boundary after the target word at position trgtWordPos.
	 * The resulting longer target language word is then aligned to the source
	 * word aligned to the target word at position trgtWordPos+srcWordOffset.
	 * For example, removeWordBoundary(2, 0) deletes the word boundary between
	 * the 2. and 3. target word and aligns the combined word to the same
	 * source word the 2. target word was aligned before. 
	 * 
	 * @param trgtWordPos position of the word boundary to delete
	 * @param srcWordOffset alignment point which should be used for the
	 * 		resulting longer word
	 */
	public void removeWordBoundary(int trgtWordPos, int srcWordOffset) {
		if (trgtWordPos >= nTrgtWords - 1 || locks[trgtWordPos]
				|| locks[trgtWordPos + 1]) {
			return;
		}
		if (startPositions[trgtWordPos + 2] - startPositions[trgtWordPos]
				> maxWordLength) {
			return;
		}
		if (srcWordOffset != 0 && trgtWordPos + srcWordOffset < nTrgtWords) {
			realign(trgtWordPos, wordAlignment[trgtWordPos + srcWordOffset]);
		}
		// At first, adjust relTrgtPositions
		short deletedSrcWord = wordAlignment[trgtWordPos + 1];
		fertilities[deletedSrcWord]--;
		// Shift parameters
		if (trgtWordPos < nTrgtWords - 2) {
			final int nFollowUpWords = nTrgtWords - 2 - trgtWordPos; 
			System.arraycopy(startPositions, trgtWordPos + 2, startPositions,
					trgtWordPos + 1, nFollowUpWords + 1); // +1 for guardian
			System.arraycopy(wordAlignment, trgtWordPos + 2, wordAlignment,
					trgtWordPos + 1, nFollowUpWords);
			System.arraycopy(locks, trgtWordPos + 2, locks,
					trgtWordPos + 1, nFollowUpWords);
			System.arraycopy(relTrgtPositions, trgtWordPos + 2, relTrgtPositions,
					trgtWordPos + 1, nFollowUpWords);
			for (int i = trgtWordPos + 1; i < nTrgtWords; i++) {
				if (wordAlignment[i] == deletedSrcWord) {
					relTrgtPositions[i]--;
				}
			}
		} else {
			startPositions[nTrgtWords - 1] = startPositions[nTrgtWords];
		}
		// Do not resize array, just decrement nTrgtWords -> performance
		nFreeTrgtWords--;
		nTrgtWords--;
	}
	
	/**
	 * Moves the word boundary after the target word at position trgtWordPos
	 * in the given direction. For example, moveWordBoundary(3, -2) moves the
	 * word boundary between the 2. and 3. target word two phonemes to the
	 * left. If the direction parameter exceeds the word lengths in that 
	 * direction, the respective target language word is deleted.
	 *  
	 * @param trgtWordPos position of the word boundary to move
	 * @param direction direction of the movement
	 */
	public void moveWordBoundary(int trgtWordPos, int direction) {
		if (trgtWordPos >= nTrgtWords - 1 || locks[trgtWordPos]
				|| locks[trgtWordPos + 1]) {
			return;
		}
		int firstWordLength = startPositions[trgtWordPos + 1]
				- startPositions[trgtWordPos];
		int secondWordLength = startPositions[trgtWordPos + 2]
				- startPositions[trgtWordPos + 1];
		if (direction < 0) {
			if (firstWordLength <= -direction) {
				// Delete first word
				removeWordBoundary(trgtWordPos, 1);
				return;
			}
			if (secondWordLength - direction > maxWordLength) {
				return;
			}
		} else {
			if (direction >= secondWordLength) {
				// Delete second word
				removeWordBoundary(trgtWordPos, 0);
				return;
			}
			if (firstWordLength + direction > maxWordLength) {
				return;
			}
		}
		// fertilities, wordAlignment, relTrgtPositions are unchanged
		startPositions[trgtWordPos + 1] += direction;
	}
	
	/**
	 * Changes a single alignment point on word level. Aligns the target word
	 * at position trgtWordPos to the source word at position srcWordPos.
	 * 
	 * @param trgtWordPos position of the target word
	 * @param srcWordPos position of the source word
	 */
	public void realign(int trgtWordPos, int srcWordPos) {
		final int oldSrcWordPos = wordAlignment[trgtWordPos];
		if (oldSrcWordPos == srcWordPos || locks[trgtWordPos]
				|| fertilities[srcWordPos] + 1 > maxFertility) {
			return;
		}
		fertilities[oldSrcWordPos]--;
		byte newRelTrgtPos = fertilities[srcWordPos]++;
		wordAlignment[trgtWordPos] = (short) srcWordPos;
		for (int i = nTrgtWords - 1; i > trgtWordPos; i--) {
			short curSrcWordPos = wordAlignment[i];
			if (curSrcWordPos == oldSrcWordPos) {
				relTrgtPositions[i]--;
			} else if (curSrcWordPos == srcWordPos) {
				relTrgtPositions[i]++;
				newRelTrgtPos--;
			}
		}
		relTrgtPositions[trgtWordPos] = newRelTrgtPos;
	}
	
	/**
	 * Returns a string representation of this alignment.
	 * 
	 * @param e English sentence
	 * @param f French phoneme sequence
	 */
	public String toString(Sentence e, Sentence f) {
		StringBuilder b = new StringBuilder();
		Dictionary fDict = Dictionary.getSingleton(Dictionary.TRGT_DICT);
		Dictionary eDict = Dictionary.getSingleton(Dictionary.SRC_DICT);
		for (int p : f.toArray()) {
			b.append(fDict.get(p) + " ");
		}
		b.append("\n");
		String[] revAlignment = new String[countSourceWords()];
		Arrays.fill(revAlignment, " ");
		for (int pos = 0; pos < nTrgtWords; pos++) {
			String word = "f" + (pos + 1);
			int pronunLen = 0;
			for (int p = startPositions[pos]; p < startPositions[pos+1]; p++) {
				pronunLen += fDict.get(f.get(p)).length() + 1;
			}
			int blankCount = pronunLen - word.length(); 
			if (blankCount >= 0) {
				b.append(word);
				b.append(new String(new char[blankCount]).replace("\0", " "));
			} else if (pronunLen > 0) {
				b.append(word.substring(0, pronunLen));
			} else {
				Logger.getSingleton().warn("Alignment segmentation string "
					+ "generation failed: empty word at " + b.toString());
			}
			revAlignment[wordAlignment[pos]] += (pos + 1)
				+ (locks[pos] ? "l " : " ");
		}
		b.append("\n");
		for (int pos = 0; pos < countSourceWords(); pos++) {
			b.append(eDict.get(e.get(pos))
					+ " ({" + revAlignment[pos] + "}) ");
		}
		return b.toString();
	}
	
	/**
	 * Clones the alignment. The functionality equals the copy constructor.
	 * 
	 * @return the clone
	 * @see #Alignment(Alignment)
	 */
	@Override
	public Object clone() {
		return new Alignment(this);
	}
	
	/**
	 * This method can be used to explore the neighborhood around the 
	 * alignment. It collects all the alignments in a set, which can be
	 * obtained from this alignment by one of the following operations.<br>
	 * - Remove a single word boundary<br>
	 * - Realign a source language word<br>
	 * - Move a word boundary by 1 to the left or to the right<br>
	 * The neighbors are collected in a given set. The alignment itself does
	 * not count as a neighbor.
	 * 
	 * @param neighbors set in which we collect the neighbors
	 * @throws NullPointerException if <code>neighbors</code> is null 
	 */
	public void collectNeighbors(Set<Alignment> neighbors) {
		final int maxPos = nTrgtWords - 2;
		Alignment a;
		// Removing and moving
		for (int pos = 0; pos <= maxPos; pos++) {
			a = (Alignment) clone();
			a.moveWordBoundary(pos, -1);
			neighbors.add(a);
			a = (Alignment) clone();
			a.moveWordBoundary(pos, 1);
			neighbors.add(a);
			a = (Alignment) clone();
			a.removeWordBoundary(pos, 0);
			neighbors.add(a);
			if (neighbors.size() > maxNeighborhoodSize) {
				return;
			}
		}
		final int nSrcWords = countSourceWords();
		for (int srcPos = 0; srcPos < nSrcWords; srcPos++) {
			for (int trgtPos = 0; trgtPos < nTrgtWords; trgtPos++) {
				a = (Alignment) clone();
				a.realign(trgtPos, srcPos);
				neighbors.add(a);
			}
			if (neighbors.size() > maxNeighborhoodSize) {
				return;
			}
		}
	}
	
	/**
	 * Returns true if all target words are locked (i.e. the alignment cannot
	 * be changed anymore).
	 */
	public boolean isCompletelyLocked() {
		return nFreeTrgtWords == 0;
	}
	
	/**
	 * Returns true if this arrays contains no locks.
	 */
	public boolean isCompletelyFree() {
		return nFreeTrgtWords == nTrgtWords;
	}
	
	/**
	 * Fetch the locks from the given alignment and modify this alignment
	 * to meet the new locks.
	 * 
	 * @param from the alignment from which the locks are fetched
	 * @returns true on success, false if the required modifications led to
	 * 		maxFertility violations (from is copied in this case)
	 * @throws NullPointerException if from is null
	 * @throws IllegalArgumentException if the number of source language
	 * 		words or target phonemes mismatch in both alignments
	 */
	public boolean forceLocksFrom(Alignment from) 
			throws IllegalArgumentException {
		if (countSourceWords() != from.countSourceWords()
				|| countTargetPhonemes() != from.countTargetPhonemes()) {
			throw new IllegalArgumentException("Number of source words or "
					+ "target phonemes mismatch");
		}
		if (from.isCompletelyFree()) {
			return true;
		}
		int curWordIdx = 0;
		Arrays.fill(locks, false);
		for (int fromWord = 0; fromWord < from.nTrgtWords; fromWord++) {
			if (!from.locks[fromWord]) {
				continue;
			}
			short lockBeginIdx = from.startPositions[fromWord];
			short lockEndIdx = from.startPositions[fromWord + 1];
			while (startPositions[curWordIdx + 1] < lockBeginIdx) {
				curWordIdx++;
			}
			int toLockWordIdx = lockBeginIdx == 0 ? 0 : ++curWordIdx;
			// toLockWordIdx now points to the first word after lock begin
			if (startPositions[toLockWordIdx] <= lockEndIdx) {
				startPositions[toLockWordIdx] = lockBeginIdx;
			} else { // word is covering both boundaries
				cutWordToForceLock(toLockWordIdx, lockBeginIdx, lockEndIdx,
						from.wordAlignment[fromWord]);
				continue;
			}
			while(curWordIdx < nTrgtWords 
					&& startPositions[curWordIdx + 1] <= lockEndIdx) {
				curWordIdx++;
			}
			// Delete between curWordIdx and toLockWordIdx such that 
			// curWordIdx is directly after toLockWordIdx afterwards
			int toDelete = curWordIdx - toLockWordIdx - 1;
			if (toDelete < 0) { // Insert word boundary
				insertWordBoundaryToForceLock(toLockWordIdx,
						lockBeginIdx, lockEndIdx);
			} else {
				startPositions[curWordIdx] = lockEndIdx;
				deleteWordsToForceLock(toLockWordIdx, curWordIdx);
			}
			wordAlignment[toLockWordIdx] = from.wordAlignment[fromWord];
			locks[toLockWordIdx] = true;
			curWordIdx = toLockWordIdx;
		}
		nFreePhonemes = from.nFreePhonemes;
		if (!rebuildFertilitiesAndRelTrgtPositions()) {
			copy(from);
			return false;
		}
		return true;
	}
	
	/* (non-Javadoc)
	 * Helper method for forceLocksFrom().
	 */
	private void deleteWordsToForceLock(int toLockWordIdx,
			int curWordIdx) {
		int toDelete = curWordIdx - toLockWordIdx - 1;
		if (toDelete > 0) {
			// fertilities and relTrgt are rebuilt at the end, 
			// locks is built on the fly
			int nFollowUpWords = nTrgtWords - curWordIdx; 
			System.arraycopy(startPositions, curWordIdx, 
					startPositions, toLockWordIdx + 1,
					nFollowUpWords + 1);
			System.arraycopy(wordAlignment, curWordIdx, 
					wordAlignment, toLockWordIdx + 1, nFollowUpWords);
			nTrgtWords -= toDelete;
		}
	}
	
	/* (non-Javadoc)
	 * Helper method for forceLocksFrom().
	 */
	private void insertWordBoundaryToForceLock(int toLockWordIdx, 
			short lockBeginIdx, short lockEndIdx) {
		setNTrgtWords((short) (nTrgtWords + 1), (int) nTrgtWords);
		int nFollowUpWords = nTrgtWords - toLockWordIdx - 2;
		if (nFollowUpWords >= 0) {
			System.arraycopy(startPositions, toLockWordIdx + 1,
				startPositions,	toLockWordIdx + 2, nFollowUpWords + 1);
			System.arraycopy(wordAlignment, toLockWordIdx + 1,
				wordAlignment, toLockWordIdx + 2, nFollowUpWords);
		}
		startPositions[toLockWordIdx + 1] = lockEndIdx;
		if (toLockWordIdx + 1 < nTrgtWords) {
			wordAlignment[toLockWordIdx + 1] = 
					wordAlignment[toLockWordIdx];
		}
	}
	
	/* (non-Javadoc)
	 * Helper method for forceLocksFrom(). Forces a lock which needs a long
	 * word to be cut into three parts (both boundaries of the lock are covered
	 * by the same word.
	 */
	private void cutWordToForceLock(int toLockWordIdx, short lockBeginIdx,
			short lockEndIdx, short srcWord) {
		int nFollowUpWords = nTrgtWords - toLockWordIdx;
		setNTrgtWords((short) (nTrgtWords + 2), (int) nTrgtWords);
		System.arraycopy(startPositions, toLockWordIdx,
			startPositions, toLockWordIdx + 2, nFollowUpWords + 1);
		System.arraycopy(wordAlignment, toLockWordIdx, 
			wordAlignment, toLockWordIdx + 2, nFollowUpWords);
		startPositions[toLockWordIdx] = lockBeginIdx;
		startPositions[toLockWordIdx + 1] = lockEndIdx;
		wordAlignment[toLockWordIdx] = srcWord;
		wordAlignment[toLockWordIdx + 1] = 
				wordAlignment[toLockWordIdx - 1];
		locks[toLockWordIdx] = true;
	}
	

	/**
	 * Returns the index of a target word before a random free (non-locked)
	 * word boundary.
	 * 
	 * @return the index of a target word before a randomly selected free word
	 * 			boundary or -1 if {@link #isCompletelyLocked()} returns true
	 */
	public int getRandomFreeWordBoundary() {
		return getRandomFreeTargetWordIndex(nFreeTrgtWords - 2);
	}
	
	/**
	 * Returns the index of a random free (non-locked) target word.
	 * 
	 * @return the index of a randomly selected free target word or
	 * 			-1 if {@link #isCompletelyLocked()} returns true
	 */
	public int getRandomFreeTargetWordIndex() {
		return getRandomFreeTargetWordIndex(nFreeTrgtWords - 1);
	}
	
	/* Helper method for {@code getRandomFree*Word*()}.
	 */
	private int getRandomFreeTargetWordIndex(int maxIndex) {
		if (nFreeTrgtWords == 0 || maxIndex < 0) {
			return -1;
		}
		int rawTrgtWordIdx = maxIndex == 0 ? 0 : RNG.randomInt(0, maxIndex);
		int correctTrgtWordIdx = -1;
		do {
			if (!locks[++correctTrgtWordIdx]) {
				rawTrgtWordIdx--;
			}
		} while (rawTrgtWordIdx >= 0);
		return correctTrgtWordIdx;
	}
	
	/**
	 * Returns the index of a random free (non-locked) target phoneme. Do not
	 * return 0.
	 * 
	 * @return the index of a randomly selected free target phoneme or
	 * 			-1 if {@link #isCompletelyLocked()} returns true
	 */
	public int getRandomFreeTargetPhonemeIndex() {
		if (nFreePhonemes < 3) {
			return -1;
		}
		int rawPhonemeIdx = RNG.randomInt(1, nFreePhonemes - 1);
		int trgtWordIdx = -1;
		do {
			if (!locks[++trgtWordIdx]) {
				rawPhonemeIdx -= (startPositions[trgtWordIdx + 1]
						- startPositions[trgtWordIdx]);
			}
		} while (rawPhonemeIdx >= 0);
		return startPositions[trgtWordIdx +1] + rawPhonemeIdx;
	}
	
	/**
	 * This method generates a random alignment with given number of source
	 * and target words and given number of target phonemes. The alignment
	 * is generated as follows.<br>
	 * - Generate an array <code>a</code> of length <code>nTrgtWords</code>
	 * 		with random integers<br>
	 * - Normalize <code>a</code> such that it sums up to <code>trgtLen</code>.
	 * 		<code>a</code> now represents the target word lengths.<br>
	 * - For each target word, choose a random source word to align with<br>
	 * These random alignments can be used to maintain genetic diversity in
	 * evolutionary optimization algorithms.
	 * 
	 * @param nSrcWords number of source language words
	 * @param nTrgtWords number of target language words
	 * @param nTrgtPhonemes number of target language phonemes
	 * @return a random alignment with given number of words/phonemes 
	 */
	public static Alignment generateRandomAlignment(int nSrcWords,
			int nTrgtWords, int nTrgtPhonemes) {
		Alignment a = new Alignment(nSrcWords, (short) nTrgtPhonemes,
				nTrgtWords);
		int[] startPosNonNorm = new int[nTrgtWords];
		int acc = 0;
		// Word level
		short srcWordPos = 0;
		for (int pos = 0; pos < nTrgtWords; pos++) {
			int safetyCounter = 0;
			do {
				srcWordPos = (short) (nSrcWords > 1 ?
					RNG.randomInt(0, nSrcWords - 1) : 0);
				if (safetyCounter++ > 200) {
					Logger.getSingleton().warn("All source words have "
						+ "maximum fertility. Initialize population with "
						+ "empty alignments.");
					return new Alignment(nSrcWords,
							(short) nTrgtPhonemes, nTrgtWords);
				}
			} while (a.fertilities[srcWordPos] >= maxFertility);
			a.wordAlignment[pos] = srcWordPos;
			a.relTrgtPositions[pos] = a.fertilities[srcWordPos]++;
			startPosNonNorm[pos] = acc;
			acc += RNG.randomInt(1, 1000);
		}
		// Phoneme level
		short startPos = 0;
		float scale = ((float) nTrgtPhonemes) / ((float) acc);
		for (int pos = 1; pos < nTrgtWords; pos++) {
			startPos = (short) Math.min(startPos + maxWordLength,
					Math.max(startPos + 1, scale * startPosNonNorm[pos]));
			a.startPositions[pos] = startPos;
		}
		if (startPos >= nTrgtPhonemes
				|| nTrgtPhonemes - startPos > maxWordLength) {
			return generateRandomAlignment( // Generation failed, try again
					nSrcWords, nTrgtWords, nTrgtPhonemes);
		}
		assert a.isConsistent(nSrcWords, nTrgtPhonemes);
		return a;
	}
}
